package code;

import java.util.ArrayList;
import java.util.List;

public class Code54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result=new ArrayList<Integer>();
        int i,j;
        int[][] direction={{0,1},{1,0},{0,-1},{-1,0}};
        int startX=0,startY=-1;
        int n=matrix.length;
        if(n==0)
        	return result;
        int m=matrix[0].length;
        
        int cnt=1;
        boolean[][] vis=new boolean[n][m];
        
        while(cnt<=n*m){
        	/*
        	 * 绕一圈
        	 */
        	for(i=0;i<4;i++){
        		/*
        		 * 每次都走完之后，改变方向
        		 */
        		startX+=direction[i][0];
        		startY+=direction[i][1];
        		while(isLegal(startX, startY, n,m) && !vis[startX][startY]){
        			
        			cnt++;
        			result.add(matrix[startX][startY]);
        			//标记处理过的格子
        			vis[startX][startY]=true;
	        		startX+=direction[i][0];
	        		startY+=direction[i][1];
        		}
        		//回退一步
        		startX-=direction[i][0];
        		startY-=direction[i][1];
        	}
        }
        return result;
    }
    public boolean isLegal(int x,int y,int n,int m){
    	if(x>=0 && x<n && y>=0 && y<m)
    		return true;
    	return false;
    }
    public static void main(String[] args){
    	int[][] matrix={{2,5},{8,4},{0,-1}};
    	new Code54().spiralOrder(matrix);
    }
}
